// 递归前序二叉树
var preorderTraversal = function (root) {
  if (!root) return []
  const res = []
  const order = (node) => {
    res.push(node.val)
    if (node.left) {
      order(node.left)
    }
    if (node.right) {
      order(node.right)
    }
  }
  order(root)
  return res
}
// 迭代遍历前序二叉树

var preorderTraversal = function (root) {
  if (!root) return []
  const res = []
  const stack = []
  stack.push(root)
  while (stack.length) {
    const node = stack.pop()
    res.push(node.val)
    if (node.right) {
      stack.push(node.right)
    }
    if (node.left) {
      stack.push(node.left)
    }
  }

  return res
}

// 递归中序遍历二叉树

var preorderTraversal = function (root) {
  if (!root) return []
  const res = []
  const order = (node) => {
    if (node.left) {
      order(node.left)
    }
    res.push(node.val)
    if (node.right) {
      order(node.right)
    }
  }
  order(root)
  return res
}

// 迭代中序遍历二叉树

var preorderTraversal = function (root) {
  if (!root) return []
  const res = []
  const stack = []
  let temp = root
  while (temp) {
    stack.push(temp)
    temp = temp.left
  }
  while (stack.length) {
    const node = stack.pop()
    res.push(node.val)
    if (node.right) {
      let temp2 = node.right
      while (temp2) {
        stack.push(temp2)
        temp2 = temp2.left
      }
    }
  }

  return res
}

// 递归后序遍历二叉树
var preorderTraversal = function (root) {
  if (!root) return []

  const order = (node) => {
    if (node.left) {
      order(node.left)
    }
    if (node.right) {
      order(node.right)
    }
    res.push(node.val)
  }
  order(root)
  return res
}

// 迭代后序遍历二叉树
var preorderTraversal = function (root) {
  if (!root) return []
  const res = []
  const stack = []
  let temp = root
  while (temp) {
    stack.push(temp)
    temp = temp.left
  }
  let prev = null
  while (stack.length) {
    const node = stack[stack.length - 1]
    if (!node.right || (node.right && prev == node.right)) {
      prev = stack.pop()
      res.push(node.val)
    } else if (prev != node.right) {
      let temp2 = node.right
      while (temp2) {
        stack.push(temp2)
        temp2 = temp2.left
      }
    }
  }

  return res
}

// 正层序遍历二叉树
var preorderTraversal = function (root) {
  if (!root) return []
  const res = []
  const queue = []
  queue.push(root)
  while (queue.length) {
    const layerGroup = []
    const n = queue.length
    for (let i = 0; i < n; i++) {
      const node = queue.shift()
      layerGroup.push(node.val)
      if (node.left) {
        queue.push(node.left)
      }
      if (node.right) {
        queue.push(node.right)
      }
    }
    res.push(layerGroup)
  }

  return res
}
// 反层序遍历二叉树
var preorderTraversal = function (root) {
  if (!root) return []
  const res = []
  const queue = []
  queue.push(root)
  while (queue.length) {
    const layerGroup = []
    const n = queue.length
    for (let i = 0; i < n; i++) {
      const node = queue.shift()
      layerGroup.push(node.val)
      if (node.right) {
        queue.push(node.right)
      }
      if (node.left) {
        queue.push(node.left)
      }
    }
    res.unshift(layerGroup)
  }

  return res
}
